package gsw.tool.datastructure.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import gsw.tool.common.ToolShow;

/**
 * 定n个权值作为n个叶子节点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
 * 哈夫曼树是带权路径长度最短的树，权值较大的节点离根较近。
 */
public class TreeHuffman<E extends Comparable> extends TreeBinary<E> {

    public static void test() {
        TreeHuffman<Integer> tree = new TreeHuffman<Integer>();
        int[] list = new int[]{10, 1, 2, 44, 5, 5, 7, 9};
        Arrays.sort(list);
        for (Integer i : list) {
            tree.put(new Node<Integer>(i, i));
        }
        tree.recursionPre();
        List<HuffmanCode<Integer>> map = tree.getHuffmanCode();
        ToolShow.log(map.toString());
    }

    /**
     * 添加元素：添加时从小到大的权重顺序添加
     *
     * @param node 需要添加的节点
     */
    public void put(Node<E> node) {
        if (root == null) {
            root = node;
            return;
        }

        Node<E> old = root;
        //新建一个节点作为根节点
        root = new Node<E>();
        //新节点的权重=旧的根节点的权重+插入节点的权重
        root.bran = old.bran + node.bran;
        //权重小的节点放左边
        if (old.bran < node.bran) {
            root.left = old;
            root.right = node;
        } else {
            root.left = node;
            root.right = old;
        }
        old.parent = root;
        node.parent = root;
    }

    /**
     * 将哈夫曼树转为哈夫曼编码
     * 哈夫曼树每个节点都有叶子节点，最下面的分支节点有两个叶子节点，我们现在要遍历所有的叶子节点，并用0和1表示，即为哈夫曼编码。
     */
    public List<HuffmanCode<E>> getHuffmanCode() {
        Node<E> curr = root;
        if (curr == null) {
            return null;
        }
        List<HuffmanCode<E>> list = new ArrayList<>();
        String code = "";
        while (curr != null) {
            Node<E> left = curr.left;
            Node<E> right = curr.right;
            //到达叶子节点就退出
            if (left == null && right == null) {
                //只有一个节点时
                if (curr == root) {
                    list.add(new HuffmanCode<E>(curr.data, code + "0"));
                }
                break;
            }
            //如果左子节点为叶子节点，则将其取出，并用0表示，然后遍历右子节点
            if (left.left == null && right.left != null) {
                list.add(new HuffmanCode<E>(left.data, code + "0"));
                curr = right;
                code += "1";
                //如果右子节点为叶子节点，则将其取出，并用1表示，然后遍历左子节点
            } else if (right.left == null && left.left != null) {
                list.add(new HuffmanCode<E>(right.data, code + "1"));
                curr = left;
                code += "0";
                //如果左右子节点都是叶子节点，则都取出，并且遍历结束
            } else if (right.left == null && left.left == null) {
                list.add(new HuffmanCode<E>(right.data, code + "1"));
                list.add(new HuffmanCode<E>(left.data, code + "0"));
                curr = null;
            }
        }
        return list;
    }

    /**
     * 哈夫曼编码
     *
     * @param <E>
     */
    static class HuffmanCode<E> {
        E data;
        String code;

        public HuffmanCode(E data, String code) {
            this.data = data;
            this.code = code;
        }

        @Override
        public String toString() {
            return "HuffmanCode{" +
                    "data=" + data +
                    ", code='" + code + '\'' +
                    "}\n";
        }
    }

}
